package hot100;


/*
 * Author：江松
 * Date：2023/4/14 11:56
 *
 *
 删除无效的括号:搜索+剪枝
 正着想，删除哪些部分是很复杂的。因此反向思考，删除最小部分，即拼接成最长的合法串
 维护一个score，左括号+1，右括号-1，score最终为0说明合法
 剪枝操作：如果score<0说明右括号在前已经不合法，如果score>lr说明超过左括号超过太多
 其他情况可以加或者不加左括号，右括号；然后是字符就直接放入
 */

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class Main301 {

    int lr=0,mlen=-1;
    int n;
    HashSet<String>set=new HashSet<>();
    String s;

    public void dfs(int id,String cur,int score){
        //剪枝
        if(score<0||score>lr)return;
        //搜索完成
        if(id==n){
            //保证是删除最小的,也就是长度最大
            //因此每次有长度更大的答案就需要删除原来的答案
            if(score==0){
                if(cur.length()>=mlen){
                    if(cur.length()>mlen)set.clear();
                    mlen=cur.length();
                    set.add(cur);
                }
            }
            return;
        }
        char ch=s.charAt(id);
        String add=cur+String.valueOf(ch);
        if(ch=='('){
            dfs(id+1,cur,score);
            dfs(id+1,add,score+1);
        }else if(ch==')'){
            dfs(id+1,cur,score);
            dfs(id+1,add,score-1);
        }else{
            dfs(id+1,add,score);
        }
    }

    public List<String> removeInvalidParentheses(String s) {
        this.s=s;
        n=s.length();
        int l=0,r=0;
        for(int i=0;i<n;++i){
            if(s.charAt(i)=='(')l++;
            else if(s.charAt(i)==')')r++;
        }
        lr=Math.min(l,r);
        dfs(0,"",0);
        return new ArrayList<String>(set);
    }
}
